Terminal controllers are communication devices which provide an interface between a plurality of terminals and a host computer or a communication system. Each terminal connected to the controller may, at any given time, have a message to send to the host computer or another terminal. The terminals are typically connected via a common bus or coaxial cable, and thus share the same data path for transmitting messages. The purpose of the controller is to orderly and efficiently collect messages from the terminals, according to some protocol.
One of the objectives of any protocol is to allow messages to be received very quickly when only a few terminals have messages to transmit, while still allowing all messages to be transmitted within a relatively short period of time when nearly all terminals in a network have a message to transmit. In general, prior art techniques attempt to strike a balance between these two objectives. For example the controller in a polled multidrop network polls (or is enabled to receive a message from) a single terminal at one time. Thus, each individual terminal is allocated a time slot to transmit a message, whether or not the terminal has message to transmit. This method is efficient when the network is heavily loaded, because the controller spends no time in deciding which terminal to poll. However, this method is very inefficient when the network is lightly loaded. For example if only one terminal has a message to transmit but there are 64 terminals on the network, then the network is only operating at one sixty-fourth of its capacity, since all the other terminals are polled even though they do not have messages. Consequently, in a lightly loaded 64 terminal network, each message has to wait an average of 32 polls.
Other protocols logically arrange a group of terminals into a binary tree. From the "root" of the tree, the controller determines if a message is ready to be transmitted from any of the terminals. If any terminal has a message to transmit, the controller subdivides the tree in halves to determine which half has a message to transmit. This process is repeated until a single terminal has been isolated with a message to send. After the message is sent, the controller determines if the untested "halves" of the binary tree have terminals with messages to send, until all terminals have been queried. This process is efficient when there are only a few terminals with a message to transmit. In a network with 64 terminals, a single terminal with a message can be identified in 7 queries by probing 64, 32, 16, 8, 4, 2, and finally the last terminal. However, when the network is heavily loaded, this protocol is inefficient because it takes seven queries for each terminal with a message, or 448 queries if all 64 terminals have just one message. This is far more than the 64 queries needed to process all terminals under the polled multidrop protocol described above.
For a centrally controlled network (as described below), the method used by the controller to select subgroups is as follows: The controller sends a signal to all terminals in a group or subgroup, indicating to each terminal that a response should be sent back if the terminal has a message to send. This signal is known as a "probe." If the controller receives a response, then it subdivides the group into two subgroups and probes the first group. If a response is received again, the process is duplicated. If not, the second group is probed. The controller cannot distinguish the number of responses it receives from a probe, only the existence of at least one response. When a terminal with a message is utlimately identified by repeated group subdivisions, the controller sends that terminal a "poll," indicating that it is ready to receive the actual message from the terminal. This is known as a probe/poll protocol.
The protocol described in Brophy (U.S. Pat. No. 4,071,908 incorporated herein by reference) attempts to strike a balance between light-load and heavy-load network efficiency by beginning probes to terminals at levels below the "root" of the binary tree, depending on how heavily the network is loaded. (See FIG. 5) For example, if a 64 terminal network is fully loaded the protocol will probe each terminal individually at the lowest level, in a manner identical to the polled multidrop protocol. If the network is only moderately loaded, the the protocol may begin probing at a middle level, probing 4 terminals at a time, for example. If any one of the four terminals has a message to transmit, that group will be subdivided and probed again, as described above. The process will be repeated for the remaining 15 groups of 4 terminals. At the end of each cycle, the time it took to poll all the terminals is determined and used to calculate which level in the tree structure polling should begin for the next cycle. If the previous cycle took a long time to complete, (indicating heavy usage,) the probing will start at a low level, while a short cycle time will cause an initial probe to begin at a higher level, or even the root of the tree.
There are several problems with this protocol. First, additional hardware is required to keep track of the time required for each cycle, and to compute the appropriate probing level in the tree for each cycle. The time required for these computations also cuts into overall processing time overhead. Second, sporadic cycle delays caused by poor design or noise in the network can "fool" the protocol into thinking that there are more messages on the network than there really are, causing the network to probe terminals at an inappropriately low level. Third, the protocol is inefficient for multiple access networks, as described below.
Terminal controllers for implementing a networking protocol can be divided into two classes: those utilizing centralized control (CC) and those utilizing distributed control (DC). The primary difference between these two classes is that a centralized controller must poll (or address a specific terminal) before the terminal can send a message. On the other hand, in a distributed controlled network, each terminal can independently implement the protocol, since each message includes the address of the sending and recipient device. Thus, every terminal may independently act as controller and constantly monitor the messages on the network. However, the ability to actually receive and transmit messages is limited because only one message can be sent over the network at one time. Thus if two terminals attempt to transmit simultaneously, their messages become scrambled on the network. Such an event is referred to as a "collision." In this case, each controller recognizes that more than one terminal is attempting to send a message, but is unable to identify the specific source or content of the messages.
As described in Capetanakis, "Contention Resolving Tree Algorithms for Multiple Access Channels," IEEE CH 1435-7/79/0000 (1979) incorporated herein by reference, a probing/polling protocol such as that described by Brophy can also be used in a DC multiple access network. This can result in a significant increase in network efficiency. For example, if there is only one terminal with a message to send in DC network, that message will be received and processed by the controller when it probes the root of a binary tree. Thus, the subsequent subdivisions of the tree to find the single terminal sending the message are unnecessary. A subdivision is necessary only when two or more terminals attempt to send a message at the same time, resulting in a collision.